from typing import *
from math import inf


class Solution:

    def minExtraChar(self, s: str, dictionary: List[str]) -> int:
        n = len(s)
        f = [inf] * (n + 1)
        f[n] = 0
        h = set(dictionary)
        for i in range(n - 1, -1, -1):
            f[i] = f[i + 1] + 1
            for j in range(i, n):
                if s[i:j + 1] in h:
                    f[i] = min(f[i], f[j + 1])
        return f[0]


a = 1
for i in range(1,10):
    a *= i
print(a * 9)